package com.ifreeee.sort.radixsort.counting;

import com.ifreeee.sort.quicksort.QuickSort;
import com.ifreeee.sort.radixsort.RadixSort;
import com.ifreeee.utils.RandomUtils;
import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * 基数排序（结合计数排序的空间优化）
 * 深入理解 基数排序：
     * 1. 关于排序算法稳定性的作用：
         * 案例问解：
         * 问：
             * 我要按照对象的 金额字段排序；对于金额相同的，我要按照对象的 时间字段来排序；
         * 解：
             * 我先按照时间排序，再使用稳定的排序算法按照金额排序，由于 稳定性排序不会打乱相同值原有顺序，所以该题已解。
     * 2. 关于 int型 排序问题，其实可以分解为（以 0 - 999 数据范围为例）：
         * 1. 我要按照百位数排序；
         * 2. 对于百位数相同的，我要按照十位数排序；
         * 3. 对于百位十位都相同的，我要按照个位数排序。
     * 3. 那么解法应该已经很好分析了：
         * 从最后一位开始使用稳定性排序（这里选用计数排序Counting Sort），一直到最高位，最终实现集合有序。
     * 4. 基数排序是借助稳定性排序不会打乱相同值原有顺序的特点，在对高位排序时不会打乱低位已经排好的顺序；
 * 选用计数排序 排序位值 的理由：
     * 1. 基数排序对于基数 baseNum 的选择不会太大，要排序的位值 重复率高，故而位值适合使用计数排序。
     * 2. 计数排序时间复杂度O(n)，是稳定排序算法。
     * 3. 是基数排序空间复杂度的 最优方案：
         * O(n + baseNum)  数据规模 + 基数
 * 关于基数的选择是个问题：
     * baseNum越大，越利于基数排序，baseNum越小 越利于计数排序；要取一个相对合适的值。
 * 代码思路：
     * 1. 第一步，我要获取数组的相关信息
         * 1. 是否包含负数？
         * 2. 最大位数是多少？
         * 3. 找最大值和最小值，判断最小值小于0得到问题一的答案；问题二就不详细说了，很容易
     * 2. 第二步，写两个方法
         * 一个用于处理有负数的基数排序；
         * 一个处理没有负数的基数排序；
         * 参数：数组 arr 、 最大位数 maxlenght 、 基数 baseNum
         * 后面以没有负数的基数排序方法为例 --->
     * 3. 第三步，我要开辟相关的辅助空间
         * 1. 计数数组 new int[baseNum] 用于计数
         * 2. 创建一个新数组 new int [arr.length]
         * 3. 其他相关辅助 变量 i j k ...
     * 4. 遍历 maxlenght 次
         * 1. 从最低位开始 使用计数排序，一直到最高位结束
         * 2. 遍历原数组，计数到 计数数组 中；再处理好 计数数组
         * 3. 再次遍历原数组，按照计数 数组，按位值排好序
         * 4. 修改引用
     * 5. 最终判断，排好序的容器是否为 arr ，如果不是，则把排好序的数组copy到arr
 */
public class RadixSortByCounting {

    /**
     * 基数排序（结合计数排序的空间优化）
     *
     * @param arr     待排序数组
     * @param baseNum 基数
     */
    public static void radixSortByCounting(int[] arr, int baseNum)
    {
        int max = getMaxValue(arr);//找最大值
        int min = getMinValue(arr);//找最小值
        boolean hasNegative = min < 0;//有负数
        //先变成正数，再求出最高位数
        max = max < 0 ? -max : max;
        min = hasNegative ? -min : min;
        int maxLenght = getNumLenght(max > min ? max : min, baseNum);//最高位数
        radixSortByCountingPositive(arr, maxLenght, baseNum);
        if(hasNegative){//负数需要额外的处理

        }
    }

    /**
     * 只能处理 正数的 基数排序
     * @param arr
     * @param maxLenght
     * @param baseNum
     */
    public static void radixSortByCountingPositive(int[] arr, int maxLenght, int baseNum)
    {
        //     * 3. 第三步，我要开辟相关的辅助空间
        //         * 1. 计数数组 new int[baseNum] 用于计数
        //         * 2. 创建一个新数组 new int [arr.length]
        //         * 3. 其他相关辅助 变量 i j k ...
        int[] countArr = new int[baseNum];//计数排序用于计数
        int len = arr.length;//记录数组长度，不少地方要用到
        int[] tempArr = null;//
        int[] sourceArr = arr;//把arr的地址先给sourceArr
        int[] targetArr = new int[len];//非原地排序，开辟新的空间
        int i, j, k, v;
        //4. 遍历 maxlenght 次
        //         * 1. 从最低位开始 使用计数排序，一直到最高位结束
        //         * 2. 遍历原数组，计数到 计数数组 中；再处理好 计数数组
        //         * 3. 再次遍历原数组，按照计数 数组，按位值排好序
        //         * 4. 修改引用

        for(i = 0, j = 1; i < maxLenght; ++i, j *= baseNum){//对第 倒数 i + 1 位数排序；j辅助取第 倒数 i + 1 位数
            //计数排序开始，先遍历数组计数
            for(k = 0; k < len; ++k){
                ++ countArr[sourceArr[k] / j % baseNum /* 取倒数第i+1位数 */ ];
            }
            //处理好计数数组（下面是最难理解的一部分）
            for(v = 1; v < baseNum; ++ v){
                countArr[v] += countArr[v - 1];
            }//此时 包括v 比v小的有 countArr[v] 个
            while (-- k > -1){
                targetArr[ -- countArr[ sourceArr[k] / j % baseNum ] ] = sourceArr[k];
            }
            while (-- v > -1){//因为要重复排序，所以清零
                countArr[v] = 0;
            }
            //修改引用，arr的地址不变用于最后判断
            tempArr = sourceArr;
            sourceArr = targetArr;
            targetArr = tempArr;
        }
        //5. 最终判断，排好序的容器是否为 arr ，如果不是，则把排好序的数组copy到arr
        if(arr != sourceArr){
            while (--len > -1){
                arr[len] = sourceArr[len];
            }
        }
    }

    /**
     * 返回最大数
     *
     * @param arr 传入一个数组
     * @return 最大值
     */
    public static int getMaxValue(int[] arr)
    {
        int maxNum = arr[0];//记录最大值
        for (int value : arr) {//找最大值
            if (value > maxNum) {
                maxNum = value;
            }
        }
        return maxNum;
    }

    /**
     * 返回最小数
     *
     * @param arr 传入一个数组
     * @return 最小值
     */
    public static int getMinValue(int[] arr)
    {
        int minNum = arr[0];//记录最小值
        for (int value : arr) {//找最小值
            if (value < minNum) {
                minNum = value;
            }
        }
        return minNum;
    }

    /**
     * 获取一个数的 位数
     *
     * @param num     数
     * @param basenum 进制数
     * @return
     */
    public static int getNumLenght(int num, int basenum)
    {
        if (num == 0) {
            return 1;
        }
        int lenght = 0;//记录位数
        for (int temp = num; temp != 0; temp /= basenum) {//计算位数
            lenght += 1;
        }
        return lenght;//返回位数
    }

    /**
     * 基数排序测试
     */
    @Test
    public void test1()
    {
        Random r = new Random();//随机数对象
        int num1 = 0;//代码一的时间
        int num2 = 0;//代码二的时间
        int num3 = 0;//代码三的时间
        int len = 10000000;//测试的数据量
        int time = 2;
        for (int j = 0; j < time; j += 1) {
            //初始化操作
            int[] arr = new int[len];
            int[] arr1 = new int[len];
            int[] arr2 = new int[len];
            for (int i = 0; i < len; i += 1) {
//                int a = RandomUtils.randomNum(-len, len, r);
                int a = r.nextInt(len);
                arr[i] = a;//
                arr1[i] = a;//
                arr2[i] = a;//三个数组数据相同
            }
            //希尔排序无需初始化准备
            long t1 = System.currentTimeMillis();
            //代码一
            QuickSort.quickSort(arr);
            long t2 = System.currentTimeMillis();
            //代码二
            RadixSortByCounting.radixSortByCounting(arr1, 10000);
            long t3 = System.currentTimeMillis();
            //代码三
            Arrays.sort(arr2);
            long t4 = System.currentTimeMillis();
            num1 += (t2 - t1);
            num2 += (t3 - t2);
            num3 += (t4 - t3);
            for (int i = 0; i < len; i += 1) {
                if (arr[i] != arr1[i] || arr[i] != arr2[i]) {
                    System.out.println("错误");
                }
            }
//            System.out.println(Arrays.toString(arr));
//            System.out.println(Arrays.toString(arr1));
//            System.out.println(Arrays.toString(arr2));
        }

        System.out.println("数据量：" + len + "\n测试次数：" + time);
        System.out.println("快速排序 耗时：" + num1 + "\n基数排序 耗时：" + num2 + "\nTimSort排序 耗时：" + num3);
        /*
            数据量：100000000
            测试次数：2
            快速排序 耗时：27387
            基数排序 耗时：5490
            TimSort排序 耗时：17581

            数据量：10000000
            测试次数：2
            快速排序 耗时：2449
            基数排序 耗时：480
            TimSort排序 耗时：1571


            结论：基数排序最快，
            改进：已改进
            下一个改进方案：
                1. baseNum的大小对性能影响很大，要找一个取最优baseNum的算法；要结合负数考虑进去，避免最后一次判断下的数据搬移
                2. 负数的处理
                3. 对于细节的处理需要了解 java 字节码，才能做更好的处理
        */
    }
}

